package Blog0;

import javax.management.relation.RoleInfoNotFoundException;

// 创建该链表的类，同C语言中的结构体类似
class Node {
    public int data; // 节点的数值
    public Node next; // 对象的引用，就是地址，深度拷贝

    public Node(int data) {  // 该类的构造方法：通过构造方法，对节点的生成，以及初始化
        this.data = data;
        this.next = null;
    }

}


public class List {
    public Node pHead; // 首节点的生成


    // 头插法
    public void addFirst(int data) {
        Node node = new Node(data);
        if (this.pHead == null) {
            // 1. 只有一个首节点的存在
            this.pHead = node;
            return; // 插入完毕，停止后面的继续执行
        }

        // 2.多个节点的存在
        node.next = this.pHead;
        this.pHead = node;

    }


    //    打印单链表
    public void disPlay() {
        Node cur = this.pHead; // 首节点的拷贝，代替首节点的移动

        while (null != cur) {
            System.out.print(" " + cur.data);
            cur = cur.next;
        }
        System.out.println();
    }


    //    尾插法
    /*两种情况
    1. 该单链表为 “空”链表
    2.该单链表不为空，找尾节点
    * */
    public void addList(int data) {
        Node cur = this.pHead; // 首节点的拷贝

        if (this.pHead == null) {
            // 该单链表为空
            throw new RuntimeException("链表为空");
        }

        while (null != cur.next) {
            cur = cur.next; // 移动节点
        }
        Node node = new Node(data); // 调用构造方法，生成节点
        cur.next = node;

    }


    //    头删法
    public void deleteFirst() {
        Node cur = this.pHead.next; // 首节点的下一个节点的，拷贝，复制

        if (null == this.pHead) {
            System.out.println("空单链表不用删除");
            return;
        }

        this.pHead.next = cur.next;
        this.pHead = cur;
    }


    // 尾删法
    /*
    三种情况
    1.空链表
    2.只有一个首节点的存在
    3.多个节点存在
    * */
    public void deleteList() {
        Node node = this.pHead; // 首节点的复制，拷贝
        Node tmp = null;

//        1.空链表
        if (null == this.pHead) {
            throw new RuntimeException("空链表，无法操作");
        }

//        2.只有一个首节点的存在
        if (null == this.pHead.next) {
            this.pHead = null;
            return;
        }

//        3.多个节点存在
        while (node.next != null) {
            tmp = node;
            node = node.next; // 移动节点
        }

        tmp.next = null;
    }


    //    查找是否包含关键字 key 是否在单链表当中
    public boolean contains(int key) {
        Node node = this.pHead; // 首节点的复制拷贝

        if (null == this.pHead) {
            throw new RuntimeException("该链表为空");
        }

        while (node != null) {
            if (key == node.data) {
                return true; // 找到了，
            }
            node = node.next; // 移动节点
        }
        return false; // 该数值不存在
    }


    //    该单链表的长度
    public int size() {
        Node node = this.pHead; // 首节点复制，拷贝
        int count = 0;

        if (this.pHead == null) {
            System.out.println("空链表");
            return 0;
        }

        while (node != null) {
            count++;
            node = node.next;  // 移动节点
        }
        return count;
    }


    //    查找数值为 x 的的地址
    public Node searchIndex(int x) {

        Node cur = this.pHead;
        if (this.pHead == null) {
            throw new RuntimeException("该链表为空");
        }

        while (null != cur) {
            if (x == cur.data) {
                return cur;
            }
            cur = cur.next; // 移动节点
        }
        return null;
    }


    // 在数值为 x 的后面插入数据
  /*  * 三种情况
    1.在开头，可以复用 尾插法
    2.在尾部，可以复用 尾插法
    3.在中间，*/
    public void addIndex(int index,int data) {
        // 不存在
        if(null == searchIndex(index)){
            System.out.println("该数值的节点不存在，返回不执行");
            return;
        }

//       1. 在开头
        if(this.pHead == searchIndex(index)) {
            addList(data);
            return; // 执行完毕，
        }

//        2.在尾部
        if((searchIndex(index).next == null)) {
            addList(data);
            return; // 执行完毕
        }

        Node cur = searchIndex(index); // 该数值节点地址的,拷贝
        Node tmpNext = cur.next;  // 该数值节点的后面节点的地址
        Node node = new Node(data);  // 生成节点

        cur.next = node;
        node.next = tmpNext;

    }


/*

    删除第一个数值为 key 的节点
    三种情况：
    1.空链表，不用删了
    2.位于首节点
    3.在中间位置

*/
    public void remove(int key) {
        // 1.空链表，不用删了
        if(null == searchIndex(key)) { // 该数值节点的地址
            System.out.println("该数值的节点不存在，返回不执行");
            return; // 执行完毕
        }

        // 2.位于尾节点
        if(null == searchIndex(key).next) {  // 该数值节点的地址
            deleteList(); // 尾删法,复用
            return; // 执行完毕
        }

        // 3.为与首节点
        if(searchIndex(key) == this.pHead) {
            deleteFirst(); // 头删法,复用
            return; // 执行完毕

        }

        // 4.中间
        Node cur = searchIndex(key);
        Node copyPHead = this.pHead;

        while(copyPHead!=cur) { // 找到该数值节点的前一个节点
            copyPHead = copyPHead.next; // 移动节点
        }
      copyPHead.next = cur.next;
    }


//    删除所有数值为 key 的节点
    public void removeKey(int key) {
        Node tmp = this.pHead;
        Node cur = this.pHead.next;

        while(cur != null) {
            if(key == cur.data) { // 是该数值节点,删除
                tmp = cur.next;
                cur = cur.next; // 移动节点
            } else { // 不是该数值节点,移动
                tmp = cur;
                cur = cur.next;
            }

            if(key == this.pHead.data) {
                // 判断首节点是否为该数值的节点,是山粗
                this.pHead = this.pHead.next;
            }

        }

   }

// 清空单链表
    public void clear() {
        this.pHead = null;
    }

    public static void main(String[] args) {
        List list = new List();

        list.addFirst(9);
        list.addFirst(99);
        list.disPlay();
        list.addList(999);
        list.addList(999);
        list.disPlay();
        list.deleteFirst();
        list.deleteFirst();
        list.disPlay();
        list.deleteList();
        list.disPlay();
        System.out.println(list.contains(999));
        System.out.println(list.contains(0));
        System.out.println(list.size());
        list.addIndex(999,100);
        list.addIndex(999,99);
        list.disPlay();
        list.remove(99);
        list.remove(999);
        list.disPlay();
        list.addFirst(99);
        list.addFirst(99);
        list.addFirst(99);
        list.addFirst(99);
        list.disPlay();
        list.removeKey(99);
        list.disPlay();

        System.out.println("******************");


    }


}
